package hot100;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/9/15 17:38
 */
public class lc416分割等和子集 {


    public boolean canPartition(int[] nums) {
        return solve(nums);
    }
    public boolean solve(int nums[]) {
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 == 1) {
            return false;
        }
        return recursion(0,sum / 2,nums,new Boolean[nums.length + 1][sum / 2 + 1]);
    }

    public boolean recursion(int index, int rest, int nums[], Boolean dp[][]) {
        if (rest == 0) {
            return true;
        }
        if (index == nums.length) {
            return false;
        }
        if (dp[index][rest] != null) {
            return dp[index][rest];
        }
        boolean  ans = false;   // 先判断  choose  的话， 会快一些， 其实理解起来也不复杂
        if (rest - nums[index] >= 0) {
            ans = recursion(index + 1, rest -nums[index],nums,dp);
        }


        if (ans) {
            return true;
        }
        ans = recursion(index + 1, rest, nums, dp);
        return dp[index][rest] = ans;
    }

}
